package graph.directed.topological;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

import graph.unweighted.CandyGraph;
/**
 * 
 * @Title: CandyTopoLogicalSort1.java 
 * @Package graph.directed.topological 
 * @Description: 使用队列和计算图中顶点为0的度完成拓扑排序
 * @author CandyWall   
 * @date 2021年1月22日 下午6:56:47 
 * @version V1.0
 */
public class CandyTopoLogicalSort1 {
    private CandyGraph graph;
    private boolean hasLoop;    // 有向图中是否有环

    public CandyTopoLogicalSort1(CandyGraph graph) {
        if(!graph.isDirected()) {
            throw new IllegalArgumentException("拓扑排序只能用于有向图！");
        }
        this.graph = graph;
    }
    
    /**
     * 获取拓扑排序序列
     * @return
     */
    public ArrayList<Integer> getTopologicalSortOrder() {
        ArrayList<Integer> res = new ArrayList<>();
        // 获取图中所有顶点的入度
        int[] inDegrees = new int[graph.getVertex_num()];
        // 创建一个队列，用来存储需要处理的度为0的顶点
        Queue<Integer> queue = new LinkedList<>();
        for(int v = 0; v < graph.getVertex_num(); v++) {
            inDegrees[v] = graph.getInDegree(v);
            if(inDegrees[v] == 0) {
                queue.add(v);
            }
        }
        
        while(!queue.isEmpty()) {
            Integer cur = queue.remove();
            res.add(cur);
            for(int next : graph.adjacentVertexes(cur)) {
                inDegrees[next]--;
                if(inDegrees[next] == 0) {
                    queue.add(next);
                }
            }
        }
        
        // 判断是否有环
        if(res.size() != graph.getVertex_num()) {
            hasLoop = true;
            //res.clear();
        }
        
        return res; 
    }
    
    public boolean hasLoop() {
        return hasLoop;
    }
    
    public static void main(String[] args) {
        CandyGraph graph1 = new CandyGraph("testData/directed/topological/graph1.txt", true);
        CandyTopoLogicalSort1 sort1 = new CandyTopoLogicalSort1(graph1);
        System.out.println(sort1.getTopologicalSortOrder());
        if(sort1.hasLoop()) {
            System.out.println("有向图中检测到环，无法完成拓扑排序！");
        }
        CandyGraph graph2 = new CandyGraph("testData/directed/topological/graph2.txt", true);
        CandyTopoLogicalSort1 sort2 = new CandyTopoLogicalSort1(graph2);
        System.out.println(sort2.getTopologicalSortOrder());
        if(sort2.hasLoop()) {
            System.out.println("有向图中检测到环，无法完成拓扑排序！");
        }
    }
    
}
